#include <vector>
using namespace std;

// 方法1 树状数组
class NumArray {
  vector<int> treeArray;
  vector<int> originalNums;
  int lowbit(int x) { return x & (-x); }
  int sumTo(int idx) {
    idx++;
    int res = 0;
    for (; idx > 0; idx -= lowbit(idx)) {
      res += treeArray[idx];
    }
    return res;
  }

public:
  NumArray(vector<int> &nums) {
    int length = nums.size();
    originalNums = nums;
    treeArray.resize(length + 1, 0);
    for (int i = 0; i < length; ++i) {
      for (int idx = i + 1; idx <= length; idx += lowbit(idx)) {
        treeArray[idx] += nums[i];
      }
    }
  }

  void update(int index, int val) {
    index++;
    int delta = val - originalNums[index - 1], length = treeArray.size();
    originalNums[index - 1] = val;
    for (int idx = index; idx < length; idx += lowbit(idx)) {
      treeArray[idx] += delta;
    }
  }

  int sumRange(int left, int right) {
    if (left == 0) {
      return sumTo(right);
    } else {
      return sumTo(right) - sumTo(left - 1);
    }
  }
};
